#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

// 定义多项式的节点结构
typedef struct PolyNode {
    int coef; // 系数
    int expon; // 指数
    struct PolyNode *next; // 指向下一个节点的指针
} PolyNode;

// 创建多项式
PolyNode* createPolynomial() {
    PolyNode *head = (PolyNode *)malloc(sizeof(PolyNode));
    head->next = NULL;

    int n;
    printf("请输入多项式的项数：");
    scanf("%d", &n);

    PolyNode *tail = head;
    for (int i = 0; i < n; i++) {
        PolyNode *node = (PolyNode *)malloc(sizeof(PolyNode));
        printf("请输入第%d项的系数和指数（用空格隔开）：", i + 1);
        scanf("%d %d", &(node->coef), &(node->expon));
        node->next = NULL;
        tail->next = node;
        tail = node;
    }

    return head;
}

// 多项式相加
PolyNode* addPolynomials(PolyNode *poly1, PolyNode *poly2) {
    PolyNode *sum = (PolyNode *)malloc(sizeof(PolyNode));
    sum->next = NULL;
    PolyNode *tail = sum;
    poly1 = poly1->next;
    poly2 = poly2->next;

    while (poly1 && poly2) {
        if (poly1->expon > poly2->expon) {
            PolyNode *node = (PolyNode *)malloc(sizeof(PolyNode));
            node->coef = poly1->coef;
            node->expon = poly1->expon;
            tail->next = node;
            tail = node;
            poly1 = poly1->next;
        } else if (poly1->expon < poly2->expon) {
            PolyNode *node = (PolyNode *)malloc(sizeof(PolyNode));
            node->coef = poly2->coef;
            node->expon = poly2->expon;
            tail->next = node;
            tail = node;
            poly2 = poly2->next;
        } else {
            int coef_sum = poly1->coef + poly2->coef;
            if (coef_sum != 0) {
                PolyNode *node = (PolyNode *)malloc(sizeof(PolyNode));
                node->coef = coef_sum;
                node->expon = poly1->expon;
                node->next = NULL;
                tail->next = node;
                tail = node;
            }
            poly1 = poly1->next;
            poly2 = poly2->next;
        }
    }

    tail->next = poly1 ? poly1 : poly2;

    return sum;
}

// 打印多项式
void printPolynomial(PolyNode *poly) {
    poly = poly->next;
    while (poly) {
        printf("%dx^%d", poly->coef, poly->expon);
        poly = poly->next;
        if (poly) {
            printf(" + ");
        }
    }
    printf("\n");
}

// 释放多项式
void freePolynomial(PolyNode *poly) {
    PolyNode *temp;
    while (poly) {
        temp = poly;
        poly = poly->next;
        free(temp);
    }
}

int main() {
    SetConsoleOutputCP(65001);

    printf("请输入第一个多项式：\n");
    PolyNode *poly1 = createPolynomial();

    printf("\n请输入第二个多项式：\n");
    PolyNode *poly2 = createPolynomial();

    printf("\n第一个多项式：");
    printPolynomial(poly1);
    printf("第二个多项式：");
    printPolynomial(poly2);

    PolyNode *sum = addPolynomials(poly1, poly2);
    printf("\n两个多项式的和：");
    printPolynomial(sum);

    // 释放内存
    freePolynomial(poly1);
    freePolynomial(poly2);
    freePolynomial(sum);

    return 0;
}
